﻿#define _CRT_SECURE_NO_WARNINGS 1
/*汉诺塔问题*/
//#include <stdio.h>
///*汉诺塔（Tower of Hanoi），又称河内塔。源自印度古老传说
//的一个游戏，大梵天创造世界的时候做了三根金刚石柱子，在一
//根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令
//婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
//并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能
//移动一个圆盘。*/
//void move(char a, char c)
//{
//    printf("%c->%c\n", a, c);
//}
//void toh(int n, char a, char b, char c)
//{
//    if (n == 1)//只有一个圆块的情况
//        move(a, c);
//    else
//    {
//        toh(n - 1, a, c, b);//n-1个圆盘，a借助c移到b上
//        move(a, c);//a移到c上
//        toh(n - 1, b, a, c);//n-1个圆盘，b借助a，移到c上
//    }
//}
//int main()
//{
//    int n=0;
//    printf("请输入圆盘数：");
//    scanf("%d", &n);//输入初始位置的圆盘数
//    toh(n, 'a', 'b','c');
//    return 0;
//}
/* 青蛙跳台阶
 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。
 求该青蛙跳上一个n级的台阶总共有多上种跳法。*/
#include <stdio.h>
int dance_frog(int n)
{
    if (n == 1)//只有1个台阶时，一种方法
        return 1;
     if (n == 2)//2个台阶时，两种方法
        return 2;
     if (n == 3)
         return 3;
  if(n>3)//4个台阶时5种选择,5个台阶时8个选择，找到规律fan=fan（n-1）+fan(n-2)
         return dance_frog(n - 1)+ dance_frog(n - 2);//采用递归的方法
}
int main()
{
    int n,sum=0;
    printf("一共多少个台阶：");
        scanf("%d", &n);
        sum=dance_frog(n);//求有多少种方法
        printf("%d", sum);
    return 0;
}
